package q241_diffWaysToCompute;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    Map<String, List<Integer>> map = new HashMap<>();
    /*
    一道分治算法的典型题
    分治代表着我们将问题分为对应的多块 每块采用一个相同的方法来解决 最后合并得到需要的答案
    也就是一种递归的特殊形式
    例如此题 我们考虑一个算式 1*2-3*4
    当我们到达第一个*符号时，就开始分块讨论 首先对于第一块（1）不需其他操作 直接加入答案集res
    而对于(2-3*4) 则会因为括号的不同位置产生不同的答案 所以就变成了第一块结果集与第二块结果集不同答案组合的一种结果
    即为分治的解法
    此题还使用了一个备忘录 也就是hashMap来记录字符串 如果一个字符串已经出现在了map的key中则可以直接调用其对应的结果集
    不需要重复的计算 例如 1+2-1+2-1+2随着分治的进行 会拆分出多个1+2 而其在map中有记录 所以可以直接减少重复的计算
     */
    public List<Integer> diffWaysToCompute(String expression) {
        if (map.containsKey(expression)) return map.get(expression);

        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < expression.length(); i++) {
            if (isOperation(expression.charAt(i))) {
                List<Integer> l = diffWaysToCompute(expression.substring(0, i));
                List<Integer> r = diffWaysToCompute(expression.substring(i + 1));

                for (Integer l_ans : l) {
                    for (Integer r_ans : r) {
                        if (expression.charAt(i) == '+') {
                            res.add(l_ans + r_ans);
                        } else if (expression.charAt(i) == '-') {
                            res.add(l_ans - r_ans);
                        } else {
                            res.add(l_ans * r_ans);
                        }
                    }
                }
            }
        }
        // 需要注意一点 如果res为空 说明此时expression没有运算符号 只有一个数字 也要加入到res中
        if (res.isEmpty()) res.add(Integer.parseInt(expression));
        map.put(expression, res);
        return res;
    }

    private boolean isOperation(char c) {
        return c == '+' || c == '-' || c == '*';
    }


}
